package tree.test236;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/17 12:54
 */
public class Solution2 {

    // 如果以root为根的子树中包含p和q，则返回他们的最近公共祖先
    // 如果只包含p，则直接返回p
    // 如果只包含q, 则直接返回q
    // 如果都不包含， 返回null
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;

        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if(l == null) {
            // 表示左子树既没有p也没有q
            return r;
        }
        if(r == null) return l;
        return root;
    }
}
